#include <common.h>

int4* input;
int4* end;
int4* idx1;
int4* invt;

int4 items[MAX_KEY_NUM * 2];
int4* lst;


/**
 * function declarations
 */
void init();
inline int find_mid(const int tag, int4* arr, int l, int h);
inline void query(int len, const int4* keys);
void batch_query(int4* sss, int4* eee);
int intersection(int* a1, int l1, int* a2, int l2);
int intersection2(int* a1, int l1, int* a2, int l2);
void init_list(int4* arr, int len);
int merge(int* a1, int l1, int* a2, int l2);

int main(int argc, char *argv[])
{
	/*
	srand(time(0));
	
	int l1 = 5 + rand() % 100;
	int l2 = l1 + rand() % 20;
	
	int4* a1 = new int4[l1];
	int4* a3 = new int4[l1];
	int4* a2 = new int4[l2];
	
	
	init_list(a1, l1);
	init_list(a2, l2);
	for(int i = 0; i < l1; i++)
	{
		a3[i] = a1[i];
	}
	
	show_list(a1, l1);
	show_list(a2, l2);
	
	int n = merge(a1, l1, a2, l2);
	show_list(a1, n);
	n = intersection(a3, l1, a2, l2);
	show_list(a1, n);*/
	

	init();
	
	tv t1 = get_time();
	batch_query(input, end);
	tv t2 = get_time();
	
	tv t = time_diff(t2, t1);
	
	cout<<t.tv_sec<<", "<<t.tv_usec<<endl;
	
	free(input);
	free(idx1);
	free(invt);
	return 0;
}

void init_list(int4* arr, int len)
{
	int4 n = 0;
	for(int i = 0; i < len; i++)
	{
		n += rand() % 10;
		arr[i] = n;
	}
}


void init()
{
	input = (int4*) load_file(finput);
	idx1	= (int4*) load_file(fidx1);
	invt	= (int4*) load_file(finvt);
	
	end = input + get_file_size(finput) / sizeof(int4) * sizeof(byte1);
	lst = new int4[MAX_LIST_LEN];
}

int merge(int* a1, int l1, int* a2, int l2)
{
	int i = 0;
	int j = 0;
	int n = 0;
	
	for(; i < l1 && j < l2;)
	{
		if(a1[i] == a2[j])
		{
			a1[n++] = a1[i];
			i++;
			j++;
		}
		else if(a1[i] < a2[j])
		{
			i++;
		}
		else
		{
			j++;		
		}
	}
	
	return n;
}

inline int intersection(int4* a1, int l1, int4* a2, int l2)
{
	int n = 0;
	int *a = a1;

	for(; l1 > 0 && l2 > 0;)
	{
		int pos = fw_search2(a1[0], a2, l2);
		
		if(pos < 0)
		{
			pos = -pos - 1;
			a2 += pos;
			l2 -= pos;
		}
		else
		{
			a[n++] = a1[0];
			a2 += (pos + 1);
			l2 -= (pos + 1);
		}
		a1++;
		l1--;
		//swap(a1, a2);
		int* t = a1;
		a1 = a2;
		a2 = t;
		
		swap(l1, l2);
		//int x = l1;
		//l1 = l2;
		//l2 = x;
	}

	return n;
}

int intersection2(int* a1, int l1, int* a2, int l2)
{
	int n = 0;
	int n2 = 0;
	int *a = a1;
	int ll = l1;

	while(1)
	{
		if(!(l1 > 0 && l2 > 0)) break;
		
		int pos = fw_search2(a1[0], a2, l2);
		
		if(pos < 0)
		{
			pos = -pos - 1;
			a2 += pos;
			l2 -= pos;
		}
		else
		{
			a[n++] = a1[0];
			a2 += (pos + 1);
			l2 -= (pos + 1);
		}
		a1++;
		l1--;

		if(!(l1 > 0 && l2 > 0)) break;
		
		pos = bw_search(a1[l1 - 1], a2, l2);
		
		if(pos < 0)
		{
			l2 = -pos;
		}
		else
		{
			a[ll - ++n2] = a1[pos];
			l2 = pos;
		}
		l1--;
		
		swap2(int*, a1, a2);
		swap(l1, l2);
		
	}

	for(int i = 0; i < n2; i++)
	{
		a[n + i] = a[ll - n2 + 1 + i];
	}
	
	return n + n2;
}


inline void query(int len, const int4* keys)
{
	for(int i = 0; i < keys[0]; i++)
	{
		lst[i] = *(invt + keys[1] + i);
	}
	
	
	int4 n = keys[0];

	for(int i = 1; i < len; i++)
	{
		n = intersection(lst, n, invt + keys[i * 2 + 1], keys[i * 2]);
		//n = merge(lst, n, invt + keys[i * 2 + 1], keys[i * 2]);
	}
	
	/*cout<<"results: "<<n<<endl;
	for(int i = 0; i < n; i++)
	{
		cout<<lst[i]<<endl;
	}*/
}

void batch_query(int4* sss, int4* eee)
{
	while(sss < eee)
	//for(int i = 0; i < 2; i++)
	{
		int n = *sss;
		sss++;
		
		for(int i = 0; i < n; i++)
		{
			int id = *sss;
			sss++;
			items[i * 2] = idx1[id * 2];
			items[i * 2 + 1] = idx1[id * 2 + 1];
		}
		
		query(n, items);
		
		//break;
	}
}

